#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int N, W;
vector<pair<int, int>> Things;
constexpr int MAXN = 100;
int dp[MAXN][MAXN];
void solve();
int main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;
        Things.emplace_back(w, v);
    };
    solve();
}

// dp[i][j] = max(dp[i + 1][j - k * w_i] + k * v_i)]
// dp[0][w]
// 注意由于k的出现, 将会导致出现三次循环
void solve() {

    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j <= W; j++) {
            for (int k = 0; j - k * Things[i].first >= 0; k++) {
                dp[i][j] = max(dp[i + 1][j - k * Things[i].first] + Things[i].second * k, dp[i][j]);
            }
        }
    }

    cout << dp[0][W] << endl;
}

// 为了防止出现三次循环, 造成计算量过大, 因此我们将会尝试将表达式进行化简
void solve2() {

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < W; j++) {
            if (j > Things[i].first) dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - Things[i].first] + Things[i].second);
            else dp[i + 1][j] = dp[i][j];
        }
    }
}